package 中等.滑动窗口;

import java.util.TreeMap;

/**
 * 给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续
 * 子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
 * 如果不存在满足条件的子数组，则返回 0 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit
 */
public class 绝对差不超过限制的最长连续子数组_1438 {

    public static void main(String[] args) {

    }

    /**
     * 滑动窗口+平衡树
     * 平衡树是有序的可以计算最大，最小值，统计每个窗口右侧为 nums[right]
     * 的最大窗口，平衡树中，key为出现的数字，value为其出现的次数，整个
     * 树统计着窗口中每个数字出现的次数，左指针left向右移动，对应的数字次数-1
     * 直到使得窗口内的最大，最小差 < limit
     */
    public int longestSubarray(int[] nums, int limit) {
        int ans = 0;
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        int left = 0, right = 0;

        while (right < nums.length) {
            treeMap.put(nums[right], treeMap.getOrDefault(nums[right], 0) + 1);

            while (treeMap.lastKey() - treeMap.firstKey() > limit) {
                treeMap.put(nums[left], treeMap.get(nums[left]) - 1);
                if (treeMap.get(nums[left]) == 0) {
                    treeMap.remove(nums[left]);
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
            right++;
        }

        return ans;
    }

}
